package com.ljx.offer;

import java.util.LinkedList;
import java.util.List;

/**
 * @author 李捷禧
 * Date: 2023/4/5
 * ClassName: C_34
 */

public class C_34 {

    /**
     * res记录结果
     * path记录每次返回得到的数组
     */
       List<List<Integer>> res = new LinkedList<>();
       LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root,target);
        return res;
    }

    /**
     * 先序遍历直到target == 0 && root.left == null && root.right == null
     * 证明找到了根节点到叶子节点的值相加等于target
     * 再从左到右进行遍历
     * @param root
     * @param target
     */
    private void recur(TreeNode root, int target) {
        if(root == null) return;
        path.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null){
            res.add(new LinkedList<>(path));
        }
        recur(root.left,target);
        recur(root.right,target);
        path.removeLast();
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
